//#define _CRT_SECURE_NO_WARNINGS 1
//#include<stdio.h>
//#define N 1000001
//int arr[N];
//int tmp[N];
//int n = 0;
////void quick_sort(int arr[], int l, int r)
////{
////    if (l >= r)
////        return;
////    int i = l - 1;
////    int j = r + 1;
////    int x = (r + l) >> 1;
////    while (i < j)
////    {
////        do i++; while (arr[i] < arr[x]);
////        do j--; while (arr[j] > arr[x]);
////        if (i < j)
////        {
////            int tmp = arr[i];
////            arr[i] = arr[j];
////            arr[j] = tmp;
////        }
////    }
////    quick_sort(arr, l, j);
////    quick_sort(arr, j + 1, r);
////}
//void merge_sort(int q[], int l, int r)
//{
//    if (l >= r) return;
//
//    int mid = l + r >> 1;
//    merge_sort(q, l, mid);
//    merge_sort(q, mid+1, r);
//
//    int k = 0,i = l,j = mid + 1;
//    while (i <= mid && j <= r)
//    {
//        if (q[i] < q[j]) tmp[k++] = q[i++];
//        else tmp[k++] = q[j++];
//    }
//        
//
//        while (i <= mid) tmp[k++] = q[i++];
//        while (j <= r) tmp[k++] = q[j++];
//    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
//}
//int main()
//{
//    scanf("%d", &n);
//    int i = 0;
//    for (i = 0; i < n; i++)
//    {
//        scanf("%d", &arr[i]);
//    }
//    //quick_sort(arr, 0, n - 1);
//    merge_sort(arr, 0, n - 1);
//    for (i = 0; i < n; i++)
//    {
//        printf("%d ", arr[i]);
//    }
//    return 0;
//}